package leetcode

import kotlinetc.println

import DP.longCommonString

/**
Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

You have the following 3 operations permitted on a word:

Insert a character
Delete a character
Replace a character
Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation:
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')
 */
fun main(args: Array<String>) {


    minDistance("horse", "ros").println()
}

/**和最长公共子序列非常像
 * simliar [longCommonString]
 */
//todo  dp
fun minDistance(word1: String, word2: String): Int {


    val dp = Array(word1.length + 1, {
        Array(word2.length + 1, { 0 })
    })


    for (i in 1 until word1.length)
        dp[i][0] = i

    for (i in 1 until word2.length)
        dp[0][i] = i

    for (i in 1 until word1.length + 1)
        for (j in 1 until word2.length + 1) {

            if (word1[i - 1] ==
                    word2[j - 1])
                dp[i][j] = dp[i - 1][j - 1]
            else {
                dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i][j - 1])) + 1
            }

        }

    return dp[word1.length][word2.length]
}